package club.xiaojiawei.strings;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/3/22 7:02 PM
 * @question 424. 替换后的最长重复字符
 * @description 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
 * 在执行上述操作后，返回包含相同字母的最长子字符串的长度。
 */
public class CharacterReplacement424 {

    public static void main(String[] args) {
        String s = "BAAAB";
        int result = characterReplacement(s, 2);
        System.out.println(result);
    }

    /**
     * 练习-双指针法,优化
     * @param s
     * @param k
     * @return
     */
    public static int characterReplacement(String s, int k) {
        if (s.length() + 1 <= k){
            return s.length();
        }
        int l = 0, r = 0, max = 0;
        int[] nums = new int[26];
        while (r < s.length()){
            max = Math.max(max, ++nums[s.charAt(r) - 'A']);
            if (r - l + 1 - max > k){
                nums[s.charAt(l++) - 'A']--;
            }
            r++;
        }
        return r - l;
    }

    /**
     * 官方-双指针
     * @param s
     * @param k
     * @return
     */
    public static int characterReplacement2(String s, int k) {
        int[] num = new int[26];
        int n = s.length();
        int maxn = 0;
        int left = 0, right = 0;
        while (right < n) {
            int i = num[s.charAt(right) - 'A'];
            i++;
            maxn = Math.max(maxn, i);
            if (right - left + 1 - maxn > k) {
                num[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }

    /**
     * 民间-双指针
     * @param s
     * @param k
     * @return
     */
    public static int characterReplacement3(String s, int k){
        int n=s.length(),maxn=0;
        int c[]=new int[129];
        char ss[]=s.toCharArray();
        int right=0,left=0;
        while(right<n) {
            c[ss[right]]++;//新增元素计数+1
            maxn=Math.max(maxn,c[ss[right]]);//新增元素后更新maxn
            right++;//窗口向右扩张(预扩张)，字符串右边界为right-1
            //字符为（[left]---[right-1](length=right-left)）k个不够插缝了，整体右移动寻找新的队伍（可以是原来最长元素的下一个更长链接队伍，或者是新元素的更长队伍，整体窗口长度不变，（若新加入的是原来的最长元素则在上一部maxn已更新不会执行此步骤,若不是则平移向后查找））窗口固定！！！瞻前不顾后！！！
            while(right-left>maxn+k){
                c[ss[left]]--;//跳出元素计数-1
                left++;//向右平移
            }
        }
        return right-left;//right移动到了n
    }
}
